parsing interval or range

Hi people,

I am trying to parse some range data which is stored as string in a field called "Range". I can handle some basic ones, but not combined ones. Samples are:

Range -> I want to get
[0,5] -> 0,5
{1,2,7} -> 1,2,7
(3,10] -> 4,10
[0,5)U(10,15] -> 0,4,9,15
{-9999}U[0,9999] -> -9999,0,9999
{0, [-30,-15], [15,30]} -> 0,-30,-15,15,30

I am using a regex to handle basic ones, but I can not handle combinations: 

if(matches("([-+]*)([0-9]+),([-+]*)([0-9]+)",range)) {
    int leftNumber = intOf(range[match 1] "" range[match 2])
    int rightNumber = intOf(range[match 3] "" range[match 4])
}

 


Yes, question is obvious, how can I parse i.e. "{0, [-30,-15], [15,30]}"

Thank you.

Celal

 


celalbaba - Fri Apr 27 04:57:44 EDT 2012

Re: parsing interval or range
SystemAdmin - Mon Apr 30 10:13:41 EDT 2012

Regular expressions are not much good for nested expressions.
I don't understand some of your examples, but assuming they are typos, and you have nested brackets, look up "Recursive decent parser".

Adam

Re: parsing interval or range
celalbaba - Fri May 18 04:53:15 EDT 2012

SystemAdmin - Mon Apr 30 10:13:41 EDT 2012
Regular expressions are not much good for nested expressions.
I don't understand some of your examples, but assuming they are typos, and you have nested brackets, look up "Recursive decent parser".

Adam

Thank you Adamarla

I used recursion to handle brackets inside brackets inside brackets ... Actually "U" characters are not type-mistaken. They occur in range values to say "Union". Therefore, i ignored all characters between same level brackets, because they all mean Union.

Re: parsing interval or range
Mathias Mamsch - Fri May 18 07:31:39 EDT 2012

celalbaba - Fri May 18 04:53:15 EDT 2012
Thank you Adamarla

I used recursion to handle brackets inside brackets inside brackets ... Actually "U" characters are not type-mistaken. They occur in range values to say "Union". Therefore, i ignored all characters between same level brackets, because they all mean Union.

With regexp you can handle nested expressions if they have a fixed depth. So if you have maximum number of nested expression, you can most of the time embed it in a regular expression. However that regular expression becomes pretty complex, even if you only have one nesting level. Soon the 9 groups that you have in DXL regexp will not work any more. Therefore you need to write a parser for your expressions.

From what I see the grammar of your expressions are pretty complex. Using a BNF grammar one could write a grammar for your expressions like this: 

RangeExpression: Range [UNION Range]*
Range          : List | DelimitedRange
List           : OPENLIST ListItem [SEP ListItem]* CLOSELIST
DelimitedRange : OPENRANGE DIGIT SEP DIGIT CLOSERANGE
ListItem       : DIGIT | Range
 
// regular expressions for the tokens 
SEP       : ","
DIGIT     : "-?[0-9]+"
OPENRANGE :  "[\[(]" 
CLOSERANGE:  "[\])]" 
OPENLIST  :  "{"
CLOSELIST :  "}"
UNION     :  "U"

 


Translating that to a DXL parser is complex. The basic structure is that you need a parseFunction for ever grammar rule. For the List for example you would have:

 

 

  

bool parseList () {
    pushPosition () // Store the current parse positin 
    if (!expectToken (OPENLIST)) { popPosition(); return false }
    if (!parseRangeItem ()) { popPosition(); return false } 
 
    // parse the "[SEP RangeItem]*" part 
    while (true) {
       pushPosition() 
       if (!expectToken(SEP)) { popPosition(); break }
       if (!parseListItem())  { popPosition(); break }
       forward ()
    }
 
    // parse the CLOSELIST token
    if (!expectToken (CLOSELIST)) { popPosition(); return false }        
    forward() 
    return true
}



The expectToken function will try to parse the token using the regular expression. The pushPosition(), popPosition() store and restore the current parsing position in the string to a stack, the forward function will just remove the stored position from the stack. Then inside the parseFunctions you will need to handle the data as it comes by. In the 'ListItem' rule for example, you might process the digit depending if you are in a list or a delimitedRange and push it to the result.

While this approach seems very complex it is a structured way of handling arbitrary complex grammars. You can always try to make more complex tokens, for example the 'DelimitedRange' could also be one Token that is parsed by one regular expression. That will shorten the overall program, but will not reduce the complexity. The only way of reducing complexity is to make the grammar easier. Maybe that helps, regards, Mathias



 

 

 

Mathias Mamsch, IT-QBase GmbH, Consultant for Requirement Engineering and D00RS

 

Re: parsing interval or range
Mathias Mamsch - Fri May 18 08:22:23 EDT 2012

Mathias Mamsch - Fri May 18 07:31:39 EDT 2012

With regexp you can handle nested expressions if they have a fixed depth. So if you have maximum number of nested expression, you can most of the time embed it in a regular expression. However that regular expression becomes pretty complex, even if you only have one nesting level. Soon the 9 groups that you have in DXL regexp will not work any more. Therefore you need to write a parser for your expressions.

From what I see the grammar of your expressions are pretty complex. Using a BNF grammar one could write a grammar for your expressions like this: 

RangeExpression: Range [UNION Range]*
Range          : List | DelimitedRange
List           : OPENLIST ListItem [SEP ListItem]* CLOSELIST
DelimitedRange : OPENRANGE DIGIT SEP DIGIT CLOSERANGE
ListItem       : DIGIT | Range
 
// regular expressions for the tokens 
SEP       : ","
DIGIT     : "-?[0-9]+"
OPENRANGE :  "[\[(]" 
CLOSERANGE:  "[\])]" 
OPENLIST  :  "{"
CLOSELIST :  "}"
UNION     :  "U"

 


Translating that to a DXL parser is complex. The basic structure is that you need a parseFunction for ever grammar rule. For the List for example you would have:

 

 

  

bool parseList () {
    pushPosition () // Store the current parse positin 
    if (!expectToken (OPENLIST)) { popPosition(); return false }
    if (!parseRangeItem ()) { popPosition(); return false } 
 
    // parse the "[SEP RangeItem]*" part 
    while (true) {
       pushPosition() 
       if (!expectToken(SEP)) { popPosition(); break }
       if (!parseListItem())  { popPosition(); break }
       forward ()
    }
 
    // parse the CLOSELIST token
    if (!expectToken (CLOSELIST)) { popPosition(); return false }        
    forward() 
    return true
}



The expectToken function will try to parse the token using the regular expression. The pushPosition(), popPosition() store and restore the current parsing position in the string to a stack, the forward function will just remove the stored position from the stack. Then inside the parseFunctions you will need to handle the data as it comes by. In the 'ListItem' rule for example, you might process the digit depending if you are in a list or a delimitedRange and push it to the result.

While this approach seems very complex it is a structured way of handling arbitrary complex grammars. You can always try to make more complex tokens, for example the 'DelimitedRange' could also be one Token that is parsed by one regular expression. That will shorten the overall program, but will not reduce the complexity. The only way of reducing complexity is to make the grammar easier. Maybe that helps, regards, Mathias



 

 

 

Mathias Mamsch, IT-QBase GmbH, Consultant for Requirement Engineering and D00RS

 

whoops, i messed up the parseList code. The 'RangeItem' must be renamed to 'ListItem':
  

bool parseList () {
    pushPosition () // Store the current parse position 
    if (!expectToken (OPENLIST)) { popPosition(); return false }
    if (!parseListItem ()) { popPosition(); return false } 
 
    // parse the "[SEP ListItem]*" part 
    while (true) {
       pushPosition() 
       if (!expectToken(SEP)) { popPosition(); break } 
       if (!parseListItem())  { popPosition(); break }
       forward () // success, consume the tokens
    }
 
    // parse the CLOSELIST token
    if (!expectToken (CLOSELIST)) { popPosition(); return false }        
    forward() // success, list has been parsed. Consume the tokens.
    return true
}

 


Regards, Mathias

 

 

Mathias Mamsch, IT-QBase GmbH, Consultant for Requirement Engineering and D00RS

 

Re: parsing interval or range
celalbaba - Fri May 18 08:56:51 EDT 2012

Mathias Mamsch - Fri May 18 07:31:39 EDT 2012

With regexp you can handle nested expressions if they have a fixed depth. So if you have maximum number of nested expression, you can most of the time embed it in a regular expression. However that regular expression becomes pretty complex, even if you only have one nesting level. Soon the 9 groups that you have in DXL regexp will not work any more. Therefore you need to write a parser for your expressions.

From what I see the grammar of your expressions are pretty complex. Using a BNF grammar one could write a grammar for your expressions like this: 

RangeExpression: Range [UNION Range]*
Range          : List | DelimitedRange
List           : OPENLIST ListItem [SEP ListItem]* CLOSELIST
DelimitedRange : OPENRANGE DIGIT SEP DIGIT CLOSERANGE
ListItem       : DIGIT | Range
 
// regular expressions for the tokens 
SEP       : ","
DIGIT     : "-?[0-9]+"
OPENRANGE :  "[\[(]" 
CLOSERANGE:  "[\])]" 
OPENLIST  :  "{"
CLOSELIST :  "}"
UNION     :  "U"

 


Translating that to a DXL parser is complex. The basic structure is that you need a parseFunction for ever grammar rule. For the List for example you would have:

 

 

  

bool parseList () {
    pushPosition () // Store the current parse positin 
    if (!expectToken (OPENLIST)) { popPosition(); return false }
    if (!parseRangeItem ()) { popPosition(); return false } 
 
    // parse the "[SEP RangeItem]*" part 
    while (true) {
       pushPosition() 
       if (!expectToken(SEP)) { popPosition(); break }
       if (!parseListItem())  { popPosition(); break }
       forward ()
    }
 
    // parse the CLOSELIST token
    if (!expectToken (CLOSELIST)) { popPosition(); return false }        
    forward() 
    return true
}



The expectToken function will try to parse the token using the regular expression. The pushPosition(), popPosition() store and restore the current parsing position in the string to a stack, the forward function will just remove the stored position from the stack. Then inside the parseFunctions you will need to handle the data as it comes by. In the 'ListItem' rule for example, you might process the digit depending if you are in a list or a delimitedRange and push it to the result.

While this approach seems very complex it is a structured way of handling arbitrary complex grammars. You can always try to make more complex tokens, for example the 'DelimitedRange' could also be one Token that is parsed by one regular expression. That will shorten the overall program, but will not reduce the complexity. The only way of reducing complexity is to make the grammar easier. Maybe that helps, regards, Mathias



 

 

 

Mathias Mamsch, IT-QBase GmbH, Consultant for Requirement Engineering and D00RS

 

Thank you Mathias,

Your solution is solid-rock. I solved this parsing problem using a recursive function as I said. 

//state 0: unknown, 1: leftOpen (, 2: leftClosed [, 3: rightOpen ), 4: rightClosed, 5: element {}
int parseInterval(string range, int state) {
    for(i = 0; i < length range; i++) {
        if(currentChar == '[' || '(') {
            findClosingBracket() //']' or ')'
            handleBracketInside()
            shiftIteratorAfterBracket()
        }
        if(state == ELEMENT)
            getNumbersFromCurlyBracketsTokenizedByComma()
        if(currentChar == '{') {
            findClosingBracket() // '}'
            parseInterval(subRangeWithoutBraces, ELEMENT)
            parseInterval(restOfRange, UNKNOWN)
        }
    }
}